package leetcode;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-11-25 22:35
 **/
public class LeetCode5 {

    //O(n^3)
    public String longestPalindrome(String s) {

        if (s == null) {
            return null;
        }

        int len = s.length();
        for (int l = len; l > 0; l--) {
            for (int i = 0; i + l <= len; i++) {
                if (isPalindrome(s, i, i + l - 1)) {
                    return s.substring(i, i + l);
                }
            }
        }

        return "666";
    }

    boolean isPalindrome(String s, int left, int right) {
        while (left < right && s.charAt(left) == s.charAt(right)) {
            left++;
            right--;
        }

        return left >= right;
    }


    //中心扩展算法
    /*public String longestPalindrome(String s) {
        if (s.length() < 1) {
            return "";
        }
        int size = s.length();
        //start:最长回文串左边界
        int start = 0;
        //end:最长回文串右边界
        int end = 0;
        for (int i = 0; i < size; i++) {
            int len1 = expand(s, i, i);
            int len2 = expand(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start + 1) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return  s.substring(start, end + 1);
    }

    int expand(String str, int left, int right) {
        while (left >= 0 && right < str.length() && str.charAt(left) == str.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }*/
    //动态规划
    /*public String longestPalindrome(String s) {
        if (s.length() < 2) {
            return s;
        }
        int len = s.length();
        //dp[i][j]: 索引i-j的字符串是否是一个回文串
        boolean[][] dp = new boolean[len][len];
        for (int i = 0; i < len; i++) {
            //dp[i][i]:单个字符都属于回文串
            dp[i][i] = true;
        }
        //保存最大的回文串的左边界
        int begin = 0;
        //保存最大的回文串的长度
        int maxLength = 1;
        //chars:字符串转成字符数组
        char[] chars = s.toCharArray();

        //L:字符串长度
        for (int L = 2; L <= len; L++) {
            //i:左边界索引
            for (int i = 0; i < len; i++) {
                //j:右边界索引
                int j = i + L - 1;
                //越界终止
                if (j >= len) {
                    break;
                }

                if (chars[i] == chars[j]) {
                    //i:j的字符串长度小于3,则dp[i][j] = true,否则dp[i][j] = dp[i+1][j-1];
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                //更新最长子串信息
                if (dp[i][j] && j - i + 1 > maxLength) {
                    maxLength = j - i + 1;
                    begin = i;
                }
            }
        }
        //截取最大回文子串
        return s.substring(begin,begin + maxLength);
    }*/

}
